Természetes számok

Peano-axiómák

A természetes számok halmazát $\mathbb{N}_0$ fogja jelölni, hangsúlyozva, hogy a nulla is természetes szám: $\mathbb{N}_0 = \{0,1,2,\dots\}$. Minden $n$ természetes számnak van egy rákövetkezője, amit $\sigma(n)$, vagy egyszerűen csak $n'$ jelöl. Természetesen $n'=n+1$, de ezt most még „nem tudhatjuk”, hiszen nem definiáltuk még az összeadás műveletét, és igazából még azt sem tudjuk, hogy mi az $1$. A következőkben axiomatikusan definiáljuk az $(\mathbb{N}_0;0,\sigma)$ struktúrát, majd erre építve vezetjük be az összeadás és a szorzás műveletét, és megmutatjuk, hogy ezek rendelkeznek a jól ismert műveleti tulajdonságokkal.

(Peano-axiómarendszer)   Legyen $\mathbb{N}_0$ egy tetszőleges nemüres halmaz, legyen $0$ egy eleme ennek a halmaznak, és legyen $\sigma\colon\mathbb{N_0} \to \mathbb{N_0},\ n \mapsto n'$ egy leképezés, amelyre teljesül az alábbi három axióma:
   Furcsának tűnhet, de a definíció nem mondja meg egyértelműen, hogy mik a természetes számok (de az egyértelműség kérdésére később még visszatérünk). Természetes számoknak nevezhetjük bármely halmaz elemeit, ha adott egy kitüntetett elem (amit ugyan $0$-val jelölünk, de ez csak egy jelölés, ettől még bármi lehet ez a $0$-val jelölt elem), és adott egy $\sigma$ leképezés a halmazon úgy, hogy a fenti három Peano-axióma teljesül. A továbbiakban se fogunk foglalkozni azzal, hogy pontosan „micsodák” az $\mathbb{N}_0$ halmaz elemei, csak a (0), (INJ), (TI) axiómákra építünk. Ennek ellenére $\mathbb{N}_0$ elemeit természetes számoknak fogjuk nevezni, és a $\sigma(n)=n'$ számot $n$ rákövetkezőjének hívjuk. Használni fogjuk még az $1=0'$, $2=1'=0''$, $3=2'=1''=0'''$,… jelöléseket.
(teljes indukció)   A (TI) axióma szemléletes jelentése az, hogy a $0$-ból kiindulva minden természetes számhoz eljuthatunk a $\sigma$ leképezés elegendően sokszori alkalmazásával. Ez teszi lehetővé, hogy természetes számokról szóló állításokat teljes indukcióval bizonyítsunk. Valóban, ha $Á(n)$ egy $n$-től függő állítás (pl. az, hogy $1+2+\dots+n=n(n+1)/2$), és sikerül bizonyítanunk, hogy akkor $Á(n)$ minden $n \in \mathbb{N}_0$ esetén igaz. Hogy ezt belássuk, nem kell mást tennünk, mint tekinteni azon $n$ természetes számok halmazát, amelyekre $Á(n)$ igaz: $U:=\{n \in \mathbb{N}_0 : Á(n) \text{ igaz}\}$. A (TI) axióma ekkor garantálja, hogy $U=\mathbb{N}_0$.
   A $\sigma$ leképezés értékkészlete $\mathbb{N}:=\mathbb{N}_0 \setminus \{0\}$.
   Jelölje $\operatorname*{R}_\sigma$ a $\sigma$ leképezés értékkészletét, és legyen $U=\operatorname*{R}_\sigma \cup\, \{0\}$. Nyilván $0 \in U$, és az is világos, hogy $\forall n \in U\colon\ n' \in U$ (sőt, még az is igaz, hogy $\forall n \in \mathbb{N}_0\colon\ n' \in U$). A (TI) axiómából következik, hogy $U=\mathbb{N}_0$, vagyis $\operatorname*{R}_\sigma \cup\, \{0\} = \mathbb{N}_0$. Ennek alapján mindössze két lehetőség van: $\operatorname*{R}_\sigma = \mathbb{N}_0$ vagy $\operatorname*{R}_\sigma = \mathbb{N}$. Az előbbi a (0) axióma miatt lehetetlen, tehát $\operatorname*{R}_\sigma = \mathbb{N}$.
   A $\sigma$ leképezésnek nincs fixpontja: $\forall n \in \mathbb{N}_0\colon\ n' \neq n$.
   Teljes indukcióval bizonyítjuk az állítást. Legyen $U = \{ n \in \mathbb{N}_0 : n' \neq n\}$; azt kell belátnunk, hogy $U=\mathbb{N}_0$, és ehhez a (TI) axióma szerint az alábbi két dolgot kell igazolni.
kezdőlépés: $0 \in U$ Ez egyszerűen következik a (0) axiómából: a $0$ senkinek sem rákövetkezője, így nem lehet saját magának a rákövetkezője sem.
indukciós lépés: $n \in U \implies n' \in U$ Tfh. $n \in U$, azaz $n' \neq n$, ez az indukciós feltevés. Be kell látnunk, hogy $n'' \neq n'$. Ezt rögtön meg is kapjuk az indukciós feltevésből az (INJ) axióma segítségével: $n' \neq n \implies (n')' \neq n'$.

Természetes számok összeadása és szorzása

(természetes számok összeadása)   Természetes számok összegét a következőképpen definiáljuk:
   Talán némi magyarázatra szorul, hogy miképpen határozza meg a fenti rekurzív definíció bármely két természetes szám összegét. Rögzítsünk egy tetszőleges $a$ természetes számot, és legyen $U$ mindazon $b$ természetes számok halmaza, amelyekre $a+b$ értelmezett. A definíció (+0) része szerint $0 \in U$, a (+1) rész szerint pedig $b \in U \implies b' \in U$. Ekkor a (TI) axióma miatt $U = \mathbb{N_0}$, azaz bármilyen $b$ természetes számot hozzá tudunk adni $a$-hoz.
   Minden $n$ természetes számra $n+1 = n'$.
   Emlékezzünk rá, hogy $1$ csupán egy jelölés a $0'$ elemre. Az összeadás definíciójának (+1) részét használva kapjuk, hogy $n+1=n+0'=(n+0)'$. A (+0) rész szerint pedig $n+0=n$, és ezzel be is láttuk, hogy $n+1=n'$.
   Minden $n$ természetes számra $1+n = n'$.
   Az előző állítással ellentétben itt már szükség van a teljes indukcióra. (HF)
   A természetes számok összeadása asszociatív művelet: bármely $a,b,c$ természetes számok esetén $(a+b)+c = a+(b+c)$.
   Teljes indukcióval bizonyítjuk az állítást, mégpedig $c$ szerinti teljes indukcióval. Legyenek tehát $a$ és $b$ tetszőleges, de rögzített természetes számok, és tekintsük az $U = \{ c \in \mathbb{N}_0 : (a+b)+c=a+(b+c) \}$ halmazt. A (TI) axióma segítségével belátjuk, hogy $U=\mathbb{N}_0$.
kezdőlépés: $0 \in U$ Az összeadás definíciójának (+0) részéből következik egyrészt $(a+b)+0=a+b$, másrészt $a+(b+0)=a+b$, és így $(a+b)+0=a+(b+0)$. Ez igazolja, hogy $0 \in U$.
indukciós lépés: $c \in U \implies c' \in U$ Tfh. $c \in U$, azaz $(a+b)+c=a+(b+c)$, ez az indukciós hipotézis, röviden (IH). Be kell látnunk, hogy $(a+b)+c'=a+(b+c')$. Az összeadás definíciójának (+1) részét és az indukciós hipotézist használva ezt a következőképpen tehetjük meg: $$ (a+b)+c' \overset{(+1)}{=} ((a+b)+c)' \overset{\text{(IH)}}{=} (a+(b+c))' \overset{(+1)}{=} a+(b+c)' \overset{(+1)}{=} a+(b+c').$$
   A természetes számok összeadásának egységeleme a $0$: bármely $a$ természetes szám esetén $a+0=a=0+a$.
   Azt tudjuk, hogy $a+0=a$ (ugye?). Csábító lenne azt mondani, hogy ebből rögtön következik, hogy $0+a=a$, de még nem láttuk be, hogy az összeadás kommutatív, ezért ezt nem használhatjuk. (Valójában az épp igazolni kívánt állítást fogjuk majd felhasználni a kommutativitás bizonyításában.) De teljes indukcióval könnyen beláthatjuk, hogy $0+a=a$ teljesül minden $a$ természetes számra. Most, és a későbbiekben már nem hivatkozunk a (TI) axiómára (nem is írjuk fel az $U$ halmazt), hanem a szokásos módon írjuk le az indukciós bizonyításokat.
kezdőlépés A kezdőlépés mindössze a $0+0=0$ egyenlőség ellenőrzése, és ez (+0)-ból azonnal következik.
indukciós lépés Tfh. $0+a=a$ (IH); cél: $0+a'=a'$. Az összeadás definíciójának (+1) részét és az indukciós hipotézist használva a következőképpen érhetünk célba: $$ 0+a' \overset{(+1)}{=} (0+a)' \overset{\text{(IH)}}{=} a'.$$
   A természetes számok összeadása kommutatív művelet: bármely $a,b$ természetes számok esetén $a+b=b+a$.
   Az állítást $b$ szerinti teljes indukcióval bizonyítjuk.
kezdőlépés Azt kell igazolnunk, hogy $a+0=0+a$, és ez következik az előző állításból (ugye?).
indukciós lépés Tfh. $a+b=b+a$ (IH); cél: $a+b'=b'+a$. Az indukciós hipotézis mellett felhasználjuk a már korábban bizonyított állítások közül az összeadás asszociativitását, valamint azt, hogy $n+1=n'=1+n$ (melyik lépésben melyiket használjuk?): $$ a+b' = a+(b+1) = (a+b)+1 \overset{\text{(IH)}}{=} (b+a)+1 = b+(a+1) = b+(1+a) = (b+1)+a = b' + a.$$
   A természetes számok összeadása kancellatív művelet: bármely $a,b,c$ természetes számok esetén $a+c=b+c \implies a=b$. (Mivel már láttuk, hogy az összeadás kommutatív, elég az egyik oldali kancellativitást felírni.)
   Az állítást $c$ szerinti teljes indukcióval bizonyítjuk.
kezdőlépés Azt kell igazolnunk, hogy $a+0=b+0\!\implies\!a=b$, és ez következik (+0)-ból (ugye?).
indukciós lépés Tfh. $a+c=b+c\!\implies\!a=b$   (IH);   cél: $a+c'=b+c'\!\implies\!a=b$. Tegyük fel tehát, hogy $a+c'=b+c'$, és vezessük le ebből azt, hogy $a=b$: $$ a+c' = b+c' \overset{(+1)}{\implies} (a+c)' = (b+c)' \overset{\text{(INJ)}}{\implies} a+c = b+c \overset{\text{(IH)}}{\implies} a = b.$$
   Két természetes szám összege csak akkor nulla, ha mindkét tag nulla: bármely $a,b \in \mathbb{N}_0$ esetén $a+b=0 \implies a=b=0$.
   Tfh. $a+b=0$; cél: $a=b=0$. Ha $b \neq 0$, akkor $b$ benne van a $\sigma$ leképezés értékkészletében, azaz $b$ felírható $b=c'$ alakban alkalmas $c$ természetes számmal. Ekkor $0=a+b=a+c'=(a+c)'$ (miért?), ez pedig azt jelenti, hogy $a+c$ rákövetkezője $0$, ami ellentmond a (0) axiómának. Ha pedig $b=0$, akkor azt kapjuk, hogy $0=a+b=a+0=a$ (miért?), és ezzel kész a bizonyítás.
(természetes számok szorzása)   Természetes számok szorzatát a következőképpen definiáljuk:
   A természetes számok szorzásának zéruseleme a $0$: bármely $a$ természetes szám esetén $a \cdot 0 = 0 = 0 \cdot a$.
   Azt tudjuk, hogy $a \cdot 0=0$ (ugye?), csak azt kell igazolni, hogy $0 \cdot a = 0$. Ezt természetesen $a$ szerinti teljes indukcióval bizonyítjuk.
kezdőlépés A kezdőlépés mindössze a $0 \cdot 0=0$ egyenlőség ellenőrzése, és ez (·0)-ból azonnal következik.
indukciós lépés Tfh. $0 \cdot a=0$ (IH); cél: $0 \cdot a'=0$. Az indukciós hipotézisen kívül használjuk a szorzás definíciójának (·1) részét, és az összeadás definíciójának (+0) részét: $$ 0 \cdot a' \overset{(\cdot1)}{=} 0 \cdot a + 0 \overset{\text{(IH)}}{=} 0+0 \overset{(+0)}{=} 0.$$
   A természetes számok szorzása jobbról disztributív az összeadásra: bármely $a,b,c$ természetes számok esetén $(a+b) \cdot c = a \cdot c + b \cdot c$.
   Az állítást $c$ szerinti teljes indukcióval bizonyítjuk.
kezdőlépés A kezdőlépés mindössze az $(a+b) \cdot 0 = a \cdot 0 + b \cdot 0$ egyenlőség ellenőrzése, és ez (·0) szerint azzal ekvivalens, hogy $0 = 0+0$, ezt pedig már tudjuk (ugye?).
indukciós lépés Tfh. $(a+b) \cdot c = a \cdot c + b \cdot c$ (IH); cél: $(a+b) \cdot c' = a \cdot c' + b \cdot c'$. Az indukciós hipotézisen kívül szükségünk lesz természetesen a szorzás definíciójának (·1) részére, és még az összeadás asszociativitására és kommutativitására is: $$ (a+b) \cdot c' \overset{(\cdot1)}{=} (a+b) \cdot c + (a+b) \overset{\text{(IH)}}{=} (a \cdot c + b \cdot c) + (a+b) = (a \cdot c + a) + (b \cdot c + b) \overset{(\cdot1)}{=} a \cdot c' + b \cdot c'.$$
   A természetes számok szorzásának egységeleme az $1$: bármely $a$ természetes szám esetén $a \cdot 1 = a = 1 \cdot a$.
   Az első egyenlőség könnyen kijön: $a \cdot 1 = a \cdot 0' = a \cdot 0 + a = 0 + a =a$ (melyik lépésben mit használtunk?). Az $1 \cdot a = a$ állítást $a$ szerinti teljes indukcióval bizonyítjuk.
kezdőlépés A kezdőlépés mindössze az $1 \cdot 0 = 0$ egyenlőség ellenőrzése, és ez (·0) szerint igaz.
indukciós lépés Tfh. $1 \cdot a = a$ (IH); cél: $1 \cdot a' = a'$. Az indukciós hipotézisen és a szorzás definíciójának (·1) részén kívül használjuk még azt, hogy $a+1=a'$: $$ 1 \cdot a' \overset{(\cdot1)}{=} 1 \cdot a + 1 \overset{\text{(IH)}}{=} a + 1 = a'.$$
   A természetes számok szorzása kommutatív művelet: bármely $a,b$ természetes számok esetén $a \cdot b = b \cdot a$.
   Az állítást $b$ szerinti teljes indukcióval bizonyítjuk.
kezdőlépés A kezdőlépés mindössze az $a \cdot 0 = 0 \cdot a$ egyenlőség ellenőrzése, ez pedig valóban igaz, mert mindkét oldal értéke $0$ (hiszen láttuk már, hogy $0$ zéruselem).
indukciós lépés Tfh. $a \cdot b = b \cdot a$ (IH); cél: $a \cdot b' = b' \cdot a$. Az indukciós hipotézisen és a szorzás definíciójának (·1) részén kívül használjuk még azt, hogy $1$ multiplikatív egységelem, továbbá a jobb oldali disztributivitást és azt, hogy $b+1=b'$: $$ a \cdot b' \overset{(\cdot1)}{=} a \cdot b + a \overset{\text{(IH)}}{=} b \cdot a + a = b \cdot a + 1 \cdot a = (b+1) \cdot a = b' \cdot a .$$
   Korábban beláttuk, hogy a szorzás jobbról disztributív az összeadásra, most pedig igazoltuk, hogy a szorzás kommutatív. Ezekből következik a bal oldali disztributivitás is, és ezt fel is fogjuk használni a következő állítás bizonyításában.
   A természetes számok szorzása asszociatív művelet: bármely $a,b,c$ természetes számok esetén $(a \cdot b) \cdot c = a \cdot (b \cdot c)$.
   Az állítást $c$ szerinti teljes indukcióval bizonyítjuk.
kezdőlépés A kezdőlépés mindössze az $(a \cdot b) \cdot 0 = a \cdot (b \cdot 0)$ egyenlőség ellenőrzése, ez pedig valóban igaz, hiszen mindkét oldal értéke $0$ (miért?).
indukciós lépés Tfh. $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ (IH); cél: $(a \cdot b) \cdot c' = a \cdot (b \cdot c')$. Az indukciós hipotézisen és a szorzás definíciójának (·1) részén kívül használjuk még a bal oldali disztributivitást: $$ (a \cdot b) \cdot c' \overset{(\cdot1)}{=} (a \cdot b) \cdot c + a \cdot b \overset{\text{(IH)}}{=} a \cdot (b \cdot c) + a \cdot b = a \cdot (b \cdot c + b) \overset{(\cdot1)}{=} a \cdot (b \cdot c').$$
   Két természetes szám szorzata csak akkor nulla, ha legalább az egyik tényező nulla: bármely $a,b$ természetes számok esetén $a \cdot b = 0 \implies a=0$ vagy $b=0$.
   Tfh. $a \cdot b = 0$. Ha $b=0$, akkor készen vagyunk. Ha $b \neq 0$, akkor $b$ benne van a $\sigma$ leképezés értékkészletében, azaz van olyan $c \in \mathbb{N}_0$, amelyre $b = c'$. Ekkor (·1) szerint $a \cdot b = a \cdot c' = a \cdot c + a = 0$. Korábban láttuk már, hogy két természetes szám összege csak akkor lehet nulla, ha mindkét tag nulla. Tehát $a=0$ (és $a \cdot c$ is nulla, de erre nincs szükségünk).
   (félgyűrű) Legyenek $+$ és $\cdot$ kétváltozós műveletek a nemüres $R$ halmazon. Azt mondjuk, hogy az $(R;+,\cdot)$ struktúra félgyűrű, ha
   Félgyűrűkben (akárcsak gyűrűkben) az additív egységelemet általában $0$ jelöli. Figyeljük meg, hogy a félgyűrű definícióban (akárcsak a gyűrű definíciójában) nincs kikötve, hogy a szorzás kommutatív és egységelemes legyen. Ha ezek mégis teljesülnek, akkor kommutatív félgyűrűről, illetve egységelemes félgyűrűről beszélünk (utóbbi esetben a multiplikatív egységelemet $1$ jelöli).
   A természetes számok kommutatív egységelemes félgyűrűt alkotnak.
   A fenti állításokban igazoltunk minden műveleti tulajdonságot, ami a kommutatív egységelemes félgyűrű definíciójában szerepel.
   Gyűrűkben az additív egységelem automatikusan zéruselem is: $a \cdot 0 = 0 = 0 \cdot a$ teljesül minden $a$ elemre. Félgyűrűkben ez általában nem igaz, de — amint azt fentebb láttuk — a természetes számok félgyűrűjében igen.

A természetes számok rendezése

(természetes számok rendezése)   Tetszőleges $a,b$ természetes számok esetén legyen $a \leq b$ akkor és csak akkor, ha van olyan $x \in \mathbb{N}_0$, amelyre $b=a+x$.
   A fenti definícióban $x$ egyértelműen meghatározott, mert az összeadás kancellatív. (Később írhatjuk majd, azt, hogy $x=b-a$, de most még nem, mert „nem ismerjük” még a kivonás műveletét.) Ebből következik, hogy $a=b$ csak $x=0$ esetén teljesülhet. Tehát a szigorú rendezés így írható le:
$\forall a,b \in \mathbb{N}_0\colon\; a \lt b \iff \exists x \in \mathbb{N}\colon\ b=a+x.$
   A fent definiált $\leq$ reláció lineáris rendezés a természetes számok halmazán. Az $(\mathbb{N}_0;\leq)$ rendezett halmaz legkisebb eleme $0$.
   Meg kell mutatnunk, hogy $\leq$ reflexív, antiszimmetrikus, tranzitív és dichotóm, valamint azt, hogy $0$ a legkisebb elem. (A dichotómiát hagyjuk a végére, mert ahhoz felhasználjuk majd, hogy $0$ a legkisebb elem.) A bizonyítások során persze végig a $\leq$ reláció definíciójára építünk (de nem hivatkozunk minduntalan rá).
reflexivitás Bármely $a \in \mathbb{N}_0$ számra $a \leq a$, hiszen $a=a+0$.
tranzivitás Ha $a \leq b$ és $b \leq c$, akkor $b=a+x$ és $c=b+y$ alkalmas $x,y$ természetes számokkal. Ekkor $c=b+y=(a+x)+y=a+(x+y)$, és ebből már látszik, hogy $a \leq c$ (ugye?).
antiszimmetria Ha $a \leq b$ és $b \leq a$, akkor $b=a+x$ és $a=b+y$ alkalmas $x,y$ természetes számokkal. Ekkor $a=b+y=(a+x)+y=a+(x+y)$, és ebből következik, hogy $x+y=0$ (miért?), ami csak $x=y=0$ esetén lehetséges (miért?). Így tehát $b=a+x=a+0=a$ (ugye?).
$0$ a legkisebb elem Azt kell belátnunk, hogy $0 \leq a$ minden $a \in \mathbb{N}_0$ esetén. Ez valóban teljesül, mert $a=0+a$ (ugye?).
dichotómia A dichotómia azt jelenti, hogy bármely két természetes szám összehasonlítható. Rögzítsünk egy $n$ természetes számot, és legyen $U$ az $n$-nel összehasonlítható természetes számok halmaza: $U = \{ a \in \mathbb{N}_0 : a \geq n \text{ vagy } a \leq n \}$. Azt kell megmutatnunk, hogy $U=\mathbb{N}_0$, és ehhez a (TI) axiómát fogjuk használni.
$0 \in U$ Ez rögtön következik abból, hogy $0$ a legkisebb elem (ugye?).
$a \in U \implies a' \in U$ Tfh. $a \in U$, ekkor két lehetőség van: $a \geq n$ vagy $a \leq n$.
$a \geq n$ Ha $a \geq n$, akkor $a=n+x$ alkalmas $x$ természetes számmal, és ekkor $a'=a+1=(n+x)+1=n+(x+1)$ (ellenőrizzük minden lépés jogosságát!). Ebből következik, hogy $a' \geq n$, és így $a' \in U$.
$n \geq a$ Ha $a \leq n$, akkor $n=a+x$ alkalmas $x$ természetes számmal. Feltehetjük, hogy $x \neq 0$, hiszen az $a=n$ esetet lefedi az előző eset. Ekkor $x$ benne van a $\sigma$ leképezés értékkészletében, azaz $x$ előáll $x=y'$ alakban alkalmas $y$ természetes számmal. Így $n$-et fel tudjuk írni a következő módon: $n=a+x=a+y'=a+(y+1)=(a+1)+y=a'+y$ (ellenőrizzük minden lépés jogosságát!). Ebből következik, hogy $n \geq a'$, és így $a' \in U$.
   Bármely $a,b,c$ természetes számok esetén teljesülnek az alábbiak:
$ a \lt b \implies a + c \lt b + c\;$   és   $\;a \lt b \implies a \cdot c \lt b \cdot c$, feltéve, hogy $c \neq 0$.
   Tfh. $a \lt b$, azaz $b=a+x$ valamely $x \neq 0$ természetes számra. Ekkor $b+c=(a+x)+c=(a+c)+x$, és így $a+c \lt b+c$. A másik állítás bizonyításához tfh. $c \neq 0$, és szorozzuk be a $b=a+x$ egyenlőség mindkét oldalát $c$-vel: $b \cdot c = (a+x) \cdot c = a \cdot c + x \cdot c$. Ebből egyelőre csak annyi jön ki, hogy $a \cdot c \leq b \cdot c$. Node se $c$ se $x$ nem nulla, ezért $x \cdot c \neq 0$, és így már látjuk, hogy $a \cdot c \lt b \cdot c$.
   Bármely $a,b,c$ természetes számok esetén teljesülnek az alábbiak:
$ a \leq b \implies a + c \leq b + c\;$   és   $\;a \leq b \implies a \cdot c \leq b \cdot c$.
   Tudjuk, hogy a szigorú monotonitásból következik a monotonitás. Ezért a fenti tétel alapján majdnem készen is vagyunk, csak a szorzásnál kell a $c=0$ esetet külön megnézni, mert arra nem vonatkozott a szigorú monotonitás. Node az világos, hogy $c=0$ esetén $a \leq b \implies a \cdot c \leq b \cdot c$ (ugye?).
   A fenti tételből következik, hogy a $\leq$ reláció kompatibilis az összeadással és a szorzással, azaz $(\mathbb{N}_0;+)$ és $(\mathbb{N}_0;\cdot)$ lineárisan rendezett félcsoportok, azaz $(\mathbb{N}_0;+,\cdot)$ lineárisan rendezett félgyűrű. Ezért „szabad” egyenlőtlenségeket összeadni és összeszorozni: $$ \left. \begin{array}{c} a \leq b \\ c \leq d \\ \end{array} \right\} \implies a + c \leq b + d; \qquad \left. \begin{array}{c} a \leq b \\ c \leq d \\ \end{array} \right\} \implies a \cdot c \leq b \cdot d. $$
   A nemnulla természetes számok halmazán a szorzás kancellativ művelet: bármely $a,b,c \in \mathbb{N}$ esetén $a \neq b \implies a \cdot c \neq b \cdot c$.
   Tfh. $a \neq b$. Mivel $\leq$ dichotóm reláció, $a \lt b$ és $b \lt a$ közül (pontosan) az egyik teljesül. Az első esetben a szigorú monotonitás alapján azt kapjuk, hogy $a \cdot c \lt b \cdot c$, a második esetben pedig azt, hogy $b \cdot c \lt a \cdot c$. Ezzel mindkét esetben beláttuk, hogy $a \cdot c \neq b \cdot c$.
   Csak két olyan lineáris rendezés van a természetes számok halmazán, amivel az rendezett félgyűrűt alkot: a $\leq$ rendezés és a duálisa.
   Tfh. $\sqsubseteq$ lineáris rendezés az $\mathbb{N}_0$ halmazon, ami kompatibilis az összeadás műveletével (a szorzásra nem is lesz szükségünk). A linearitás (dichotómia) miatt $0 \sqsubseteq 1$ és $0 \sqsupseteq 1$ közül (pontosan) az egyik teljesül. Vizsgáljuk külön a két esetet.
$0 \sqsubseteq 1$ A kompatibilitást alkalmazva adogassunk $1$-et mindkét oldalhoz ($n$-szer): $$0 \sqsubseteq 1 \implies 1 \sqsubseteq 2 \implies 2 \sqsubseteq 3 \implies \cdots \implies n \sqsubseteq n+1.$$ (Itt a „$\cdots$” tulajdonképpen egy teljes indukciót „sumákol el”.) Ebből következik, hogy minden $a,b \in \mathbb{N}_0$ esetén $a \sqsubseteq b \iff a \leq b$, azaz $\sqsubseteq$ megegyezik a „szokásos” rendezéssel.
$0 \sqsupseteq 1$ A kompatibilitást alkalmazva adogassunk $1$-et mindkét oldalhoz ($n$-szer): $$0 \sqsupseteq 1 \implies 1 \sqsupseteq 2 \implies 2 \sqsupseteq 3 \implies \cdots \implies n \sqsupseteq n+1.$$ (Itt a „$\cdots$” megint egy teljes indukciót takar.) Ebből következik, hogy minden $a,b \in \mathbb{N}_0$ esetén $a \sqsubseteq b \iff a \geq b$, azaz $\sqsubseteq$ megegyezik a „szokásos” rendezés duálisával.
(a teljes indukció másik formája)   A teljes indukciónak van egy olyan változata is, ahol az indukciós hipotézisben nemcsak azt tesszük fel, hogy $n$-re teljesül az állítás, hanem azt, hogy az összes $n$-nél kisebb vagy egyenlő számra teljesül: Ennek a módszernek a helyességét úgy igazolhatjuk, hogy tekintjük az $U=\{n \in \mathbb{N}_0 : Á(0),Á(1),\dots,Á(n) \text{ igaz}\}$ halmazt. (Figyeljük meg, hogy itt az „$Á(0),Á(1),\dots,Á(n)$” részt nem tudnánk értelmezni a rendezés nélkül.) A (TI) axióma ekkor garantálja, hogy $U=\mathbb{N}_0$ (gondoljuk meg, hogy miért!).
   Természetes számok bármely nemüres halmazának van legkisebb eleme.
   Legyen $S \subseteq \mathbb{N}_0$, és tfh. $S$-nek nincs legkisebb eleme. Célunk igazolni, hogy ekkor $S$ szükségképpen az üres halmaz. Talán meglepőnek tűnik, de ezt indukcióval lehet bizonyítani. Legyen $Á(n)$ a következő állítás: „$n \notin S$”. A teljes indukció második formájával belátható, hogy $Á(n)$ igaz minden $n$ természetes számra (HF). Ebből pedig már rögtön következik, hogy $S= \emptyset$ (ugye?).
(végtelen leszállás)   A fenti tételen alapul a végtelen leszállás módszere, amit tekinthetünk a teljes indukció harmadik változatának is. Itt úgy bizonyítjuk be, hogy minden $n$ természetes számra teljesül az $Á(n)$ állítás, hogy megmutatjuk, hogy ha van olyan $n$, amelyre $Á(n)$ hamis, akkor van olyan $n$-nél kisebb $k$ természetes szám, amire $Á(k)$ szintén hamis (azaz minden ellenpéldánál van kisebb ellenpélda). Ekkor az $S = \{ n \in \mathbb{N}_0 : Á(n) \text{ hamis} \}$ halmaznak nincs legkisebb eleme, ezért a fenti tétel szerint $S= \emptyset$. Ez pedig épp azt jelenti, hogy $Á(n)$ minden $n$ természetes számra igaz. A végtelen leszállás hasznos diofantoszi egyenletek vizsgálatában, Fermat például ezzel a módszerrel bizonyította, hogy az $x^4 + y^4 = z^4$ egyenletnek nincs megoldása a pozitív egészek körében.

A Peano-axiómarendszer modelljei

Az eddigiek érvényesek a Peano-axiómarendszer minden modelljében, azaz minden olyan $(\mathbb{N}_0;0,\sigma)$ struktúrában, ami kielégíti a (0), (INJ), (TI) axiómákat. Nem is foglalkoztunk azzal, hogy mik az $\mathbb{N}_0$ hamaz elemei, csak azt használtuk, hogy teljesülnek az axiómák. Itt felmerül egy szorongató kérdés: létezik-e egyáltalán olyan $(\mathbb{N}_0;0,\sigma)$ struktúra, ami kielégíti a (0), (INJ), (TI) axiómákat, vagyis van-e egyáltalán modellje a Peano-axiómarendszernek? Ha nincs, akkor a semmiről bizonyítottunk be több, mint egy tucat állítást…

(Frege–Russell-féle konstrukció)   Gottlob Frege és Bertrand Russell a természetes számok következő konstrukcióját javasolta. Nevezzünk két (véges) halmazt ekvivalensnek, ha létezik közöttük bijekció. Ez valóban ekvivalenciareláció a véges halmazok „halmazán”, és a természetes számok nem mások, mint az ekvivalenciaosztályok: a természetes számok a véges halmazok számosságai, és két halmaznak akkor és csak akkor ugyanakkora a számossága, ha van közöttük bijekció, vagyis párbaállítás. Két probléma van ezzel a konstrukcióval:
(Neumann-féle konstrukció)   A halmazelmélet manapság általánosan elfogadott axiómarendszere a Zermelo–Fraenkel-féle axiómarendszer kiegészítve a kiválasztási axiómával, röviden ZFC. Ebben az axiómarendszerben teljesen „legális” az alábbi, Neumann János által adott konstrukció: Így például $$1 = \{ 0 \} = \{ \emptyset \},\quad 2 = \{ 0,1 \} = \{ \emptyset, \{ \emptyset \} \},\quad 3 = \{ 0,1,2 \} = \{ \emptyset, \{ \emptyset \}, \{ \emptyset, \{ \emptyset \} \} \}, \ldots.$$ Általánosan $n' = \{ 0,1,2,\dots,n\}$, azaz minden természetes szám a nála kisebb természetes számok halmaza (és felírható csak az üres halmaz segítségével). Ezzel a konstrukcióval is van egy kis probléma: ugyan megkonstruáltuk a Peano-axiómárendszer egy modelljét, de ezt egy másik axiómarendszerre alapoztuk (lásd a következő megjegyzést).
(Gödel nemteljességi tételei)   A Neumann-féle konstrukció a halmazelmélet ZFC axiómarendszerén alapszik, ezért csak akkor ad megnyugtató választ a természetes számok létezésének kérdésére, ha a ZFC axiómarendszernek van modellje. Ezzel kapcsolatban igencsak rossz hírt jelentenek Kurt Gödel nemteljességi tételei (ezeket csak „konyhanyelven” fogalmazzuk meg):

Gödel tételei szerint nem nagyon van más választásunk, mint élni azzal a „munkahipotézissel”, hogy van modellje a Peano-axiómarendszernek. Baj lenne azonban, ha több modellje is lenne, mert akkor nem lenne egyértelmű, hogy mire gondolunk, amikor természetes számokról beszélünk. Meg fogjuk mutatni, hogy izomorfia erejéig csak egy (pontosabban: legfeljebb egy) modell van. Ehhez szükségünk lesz sorozatok rekurzív definíciójára.

(sorozat)   Legyen $A$ egy tetszőleges nemüres halmaz. Az $A$ elemeiből alkotott sorozaton egy $a\colon\mathbb{N}_0 \to A,\ n \mapsto a_n$ leképezést értünk.
(rekurzióval definiált sorozat)   Legyen $A$ egy nemüres halmaz, $a \in A$ egy elem, és $f\colon A \to A$ egy leképezés. Definiáljuk az $a\colon\mathbb{N}_0 \to A$ sorozatot a következőképpen: (A (TI) axióma garantálja, hogy ezzel $a_n$ minden $n$ természetes számra értelmezett.) Az ilyen módon megadott sorozatokat rekurzív(an definiált) sorozatoknak nevezzük.
(izomorfia)   Az $(\mathbb{N}_0;0,\sigma)$ struktúra mellett legyen $(M;\heartsuit,\tau)$ egy másik hasonló struktúra, azaz egy konstanssal és egy egyváltozós művelettel „felszerelt” halmaz. Itt tehát $\heartsuit \in M$ egy tetszőleges elem és $\tau\colon M \to M, m \to m^{\ast}$ egy tetszőleges leképezés. Azt mondjuk, hogy $(\mathbb{N}_0;0,\sigma)$ és $(M;\heartsuit,\tau)$ izomorfak, ha létezik olyan $\varphi\colon \mathbb{N}_0 \to M$ leképezés, amelyre teljesülnek az alábbiak:
  1. $\varphi$ bijektív;
  2. $\varphi(0)=\heartsuit$;
  3. $\varphi(n') = \varphi(n)^{\ast}$ minden $n \in \mathbb{N}_0$ esetén.
(Az ilyen $\varphi$ leképezést izomorfizmusnak nevezzük.)
   A Peano-axiómarendszernek izomorfia erejéig legfeljebb egy modellje van. Azaz ha $(\mathbb{N}_0;0,\sigma)$ és $(M;\heartsuit,\tau)$ mindketten kielégítik a Peano-axiómákat, akkor izomorfak.
   Rekurzívan definiálunk egy $a\colon \mathbb{N}_0 \to M$ sorozatot:
  1. $a_0 = \heartsuit$;
  2. $a_{n'} = \tau(a_n) = (a_n)^{\ast}$ minden $n \in \mathbb{N}_0$ esetén.
Vezessük be a $\varphi(n)=a_n$ jelölést; ezzel így fest a fenti rekurzív definíció:
  1. $\varphi(0) = \heartsuit$;
  2. $\varphi(n') = \tau(\varphi(n)) = \varphi(n)^{\ast}$ minden $n \in \mathbb{N}_0$ esetén.
Meg fogjuk mutatni, hogy $\varphi$ izomorfizmus. (Megjegyzés: a $\varphi$ leképezés és az $a_n$ sorozat valójában egy és ugyanaz a matematikai objektum, így „pazarlás” két jelölést használni rá. Azért használunk mégis két jelölést, mert a rekurzív definíciónál az egyik, izomorfizmusoknál pedig a másik jelölés a természetesebb.) Az izomorfizmus definíciójának 2. és 3. pontja már meg is van, hiszen ezek pontosan ugyanazok, mint a fenti rekurzív definíció I. és II. pontja (ugye?). Be kell még látnunk, hogy $\varphi$ bijekció. Ehhez elegendő megmutatni, hogy $\varphi$-nek van inverze. Az inverzet szintén egy rekurzív sorozatból kapjuk meg.

Mivel $(M;\heartsuit,\tau)$ is kielégíti a Peano-axiómákat, $M$ elemeit is „ugyanolyan jogon” tekinthetjük természetes számoknak, mint $\mathbb{N}_0$ elemeit. Így használhatjuk $M$ elemeit is egy sorozat indexelésére. Rekurzívan definiálunk egy $M$ elemeivel indexelt $b_m$ sorozatot az $\mathbb{N}_0$ halmazon:

  1. $b_{\heartsuit} = 0$;
  2. $b_{m^{\ast}} = \sigma(b_m) = (b_m)'$ minden $m \in M$ esetén.
Megint áttérünk a „sorozatos” jelölésről a „leképezéses” jelölésre (ez matematikai szempontból teljesen felesleges, de „lélektani” szempontból segíthet). Legyen tehát $\psi(m)=a_m$; ezzel a jelöléssel így fest a fenti rekurzív definíció:
  1. $\psi(\heartsuit) = 0$;
  2. $\psi(m^{\ast}) = \sigma(\psi(m)) = \psi(m)'$ minden $m \in M$ esetén.

A bizonyítás befejezéséhez megmutatjuk, hogy a $\varphi$ és $\psi$ leképezések egymás inverzei. Ehhez azt kell igazolnunk, hogy $\varphi$ és $\psi$ mindkét sorrendben vett kompozíciója identikus leképezés (az $\mathbb{N}_0$, illetve az $M$ halmazon).

$\psi(\varphi(n))=n$ minden $n \in \mathbb{N}_0$ esetén Az állítást $n$ szerinti teljes indukcióval bizonyítjuk.
kezdőlépés Azt kell belátni, hogy $\psi(\varphi(0))=0$. Ez könnyen kijön a fenti I. és III. tulajdonságokból: $$\psi(\varphi(0)) \overset{\text{I}}{=} \psi(\heartsuit) \overset{\text{III}}{=} 0.$$
indukciós lépés Tfh. $\psi(\varphi(n))=n$ (IH); cél: $\psi(\varphi(n'))=n'$. Ez így vezethető le az indukciós hipotézisből, valamint a fenti II. és IV. tulajdonságokból: $$\psi(\varphi(n')) \overset{\text{II}}{=} \psi(\varphi(n)^{\ast}) \overset{\text{IV}}{=} \psi(\varphi(n))' \overset{\text{IH}}{=} n'.$$
$\varphi(\psi(m))=m$ minden $m \in M$ esetén Az állítást $m$ szerinti teljes indukcióval bizonyítjuk. (Ne feledjük: $(M;\heartsuit,\tau)$ is kielégíti a (TI) axiómát, ezért a teljes indukció itt is ugyanúgy működik, mint $\mathbb{N}_0$-ban. Csak a jelölések kicsit mások: az indukció nem $0$-ról, hanem $\heartsuit$-ről indul, az indukciós lépésben pedig nem $n$-ről $n'$-re, hanem $m$-ről $m^{\ast}$-ra lépünk.)
kezdőlépés Azt kell belátni, hogy $\varphi(\psi(\heartsuit))=\heartsuit$. Ez könnyen kijön a fenti I. és III. tulajdonságokból: $$\varphi(\psi(\heartsuit)) \overset{\text{III}}{=} \varphi(0) \overset{\text{I}}{=} \heartsuit.$$
indukciós lépés Tfh. $\varphi(\psi(m))=m$ (IH); cél: $\varphi(\psi(m^{\ast}))=m^{\ast}$. Ez így vezethető le az indukciós hipotézisből, valamint a fenti II. és IV. tulajdonságokból: $$\varphi(\psi(m^{\ast})) \overset{\text{IV}}{=} \varphi(\psi(m)') \overset{\text{II}}{=} \varphi(\psi(m))^{\ast} \overset{\text{IH}}{=} m^{\ast}.$$